%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2012 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% data section
\SetKwData{NULL}{\footnotesize{NULL}}
%%
%% input
\KwIn{An AVL tree $T$ and a vertex $v \in V(T)$.}
%%
%% output
\KwOut{The AVL tree $T$ with $v$ removed from it.}
\BlankLine
%%
%% algorithm body
$u \assign \parent[v]$\;
delete $v$ from $T$ as per Algorithm~\ref{alg:tree_data_structures:binary_search_tree_delete}\;
adjust the height of $u$\tcc*[f]{begin height adjustment}\;
$x \assign \NULL$\;
$y \assign \NULL$\;
$z \assign \NULL$\;
\While{$\parent[u] \neq \NULL$}{
  $u \assign \parent[u]$\;
  \If{\rm $\leftChild[u] \neq \NULL$ and $\rightChild[u] \neq \NULL$}{
    $h_\ell \assign \height[\leftChild[u]]$\;
    $h_r \assign \height[\rightChild[u]]$\;
    $\height[u] \assign 1 + \max(h_\ell,\, h_r)$\;
    \If{$|h_\ell - h_r| > 1$}{
      \If{$\height[\rightChild[\rightChild[u]]] = \height[\leftChild[u]] + 1$}{
        $z \assign u$\;
        $y \assign \rightChild[z]$\;
        $x \assign \rightChild[y]$\;
        trinode restructuring as per Algorithm~\ref{alg:tree_data_structures:single_left_rotation}\;
        continue with next iteration of loop\;
      }
      \If{$\height[\leftChild[\leftChild[u]]] = \height[\rightChild[u]] + 1$}{
        $z \assign u$\;
        $y \assign \leftChild[z]$\;
        $x \assign \leftChild[y]$\;
        trinode restructuring as per Algorithm~\ref{alg:tree_data_structures:single_right_rotation}\;
        continue with next iteration of loop\;
      }
      \If{$\height[\rightChild[\rightChild[u]]] = \height[\leftChild[u]]$}{
        $z \assign u$\;
        $y \assign \rightChild[z]$\;
        $x \assign \leftChild[y]$\;
        trinode restructuring as per Algorithm~\ref{alg:tree_data_structures:right_left_rotation}\;
        continue with next iteration of loop\;
      }
      \If{$\height[\leftChild[\leftChild[u]]] = \height[\rightChild[u]]$}{
        $z \assign u$\;
        $y \assign \leftChild[z]$\;
        $x \assign \rightChild[y]$\;
        trinode restructuring as per Algorithm~\ref{alg:tree_data_structures:left_right_rotation}\;
        continue with next iteration of loop\;
      }
    }
  }
  \If{$\leftChild[u] \neq \NULL$}{
    $\height[u] \assign 1 + \height[\leftChild[u]]$\;
    continue with next iteration of loop\;
  }
  \If{$\rightChild[u] \neq \NULL$}{
    $\height[u] \assign 1 + \height[\rightChild[u]]$\;
    continue with next iteration of loop\;
  }
}
